package com.atguigu.sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**
 * @author shkstart
 * @create 2021-08-21 0:21
 */
//基数排序法，8万不到一秒
public class RadixSort {
    public static void main(String[] args) {
//        int arr[] = { 53, 3, 542, 748, 14, 214};
//        radixSort(arr);
        int[] arr = new int[80000];
        for (int i=0;i<80000;i++){
            arr[i]=(int)(Math.random()*800000);
        }
        Date date1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date1);
        System.out.println("排序前的时间="+format);

        radixSort(arr);
//        System.out.println(Arrays.toString(arr));
        Date date2 = new Date();
//        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format2 = simpleDateFormat.format(date2);
        System.out.println("排序后的时间="+format2);
    }
    //基数排序法

    public static void radixSort(int[] arr){
        //创建二维数组，容纳0-9十个数字，总共十个桶，每个桶中包含选中的数字
        //为了保险起见，每个桶能够容纳的数字是按数组最多的，避免极端情况，数组全部都在一个桶中
        //典型用空间换时间
        int[][] bucket = new int[10][arr.length];
        //创建一个数组报含每个桶中装着的数字个数
        int[] bucketElementCounts = new int[10];

        //求最大值
        int max=arr[0];
        for (int i=1;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        //求最大值对应得位数
        int MaxLength=(max+"").length();

        //最大值有几位数那就循环几次
        for (int i=0, n=1;i<MaxLength;i++,n*=10){
            //对于数组全部的数字，取个位的数字填入
            for (int j=0;j<arr.length;j++){
                //取个，十。百位数
                int digitOfElement=arr[j]/n%10;
                //将数字转入桶中
                bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[j];
                //计算数组的个数
                bucketElementCounts[digitOfElement]++;
            }
            //取出每一个桶的数字
            //遍历10个桶
            //创建一个坐标，重新加载入原数组中
            int index=0;
            for (int k=0;k<bucketElementCounts.length;k++){
                //遍历每个桶的数字
                if (bucketElementCounts[k]!=0) {
                    for (int l = 0; l < bucketElementCounts[k]; l++) {
                    arr[index++]=bucket[k][l];
                    }
                }
                //每遍历一次，就需要将桶中的数字清零，避免数字叠加
                bucketElementCounts[k]=0;
            }
            //输出每一轮的数组
//            System.out.println("第"+(i+1)+"轮的数组"+ Arrays.toString(arr));
        }


    }
}
